package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Trie 208. 实现 Trie (前缀树)
 * @description: Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
 * <p>
 * 请你实现 Trie 类：
 * <p>
 * Trie() 初始化前缀树对象。
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/4/1417:41
 * @since V1.0
 */
class Trie {
    public TriNode[] arr = new TriNode[26];

    /**
     * Initialize your data structure here.
     */
    public Trie() {

    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        int index = word.charAt(0)-'a';
        arr[index] = arr[index]!=null?arr[index]:new TriNode();
        arr[index].add(word.substring(1));

    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        int index = word.charAt(0)-'a';
        if (arr[index]!=null){
            return  arr[index].search(word.substring(1));
        }
        return false;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        int index = prefix.charAt(0)-'a';
        if (arr[index]!=null){
            return  arr[index].startsWith(prefix.substring(1));
        }
        return false;
    }

    public class TriNode {
        public boolean flag;
        public TriNode[] arr = new TriNode[26];

        public TriNode() {
        }

        public void add(String str){
            if (str.length()==0){
                flag = true;
            }
            if (str.length()>0){
                int index = str.charAt(0)-'a';
                arr[index] = arr[index]!=null?arr[index]:new TriNode();
                arr[index].add(str.substring(1));
            }
        }

        public boolean search(String str) {
            if (str.length()==0){
                return flag;
            }
            int index = str.charAt(0)-'a';
            if (arr[index]!=null){
                return arr[index].search(str.substring(1));
            }
            return false;
        }

        public boolean startsWith(String str) {
            if (str.length()==0){
                return true;
            }
            int index = str.charAt(0)-'a';
            if (arr[index]!=null){
                return arr[index].startsWith(str.substring(1));
            }
            return false;
        }
    }
}